package com.sourcetrip.algorithm.sort.bubble;

import com.sourcetrip.algorithm.abs.AbstractSort;

/**
 * @author: xiaomi
 * @date: 2020/12/27
 * @description: 十大排序之 first-冒泡排序普通版本
 * 分析:
 * 将头元素与后面的元素进行比较，如果大就交换，直到最后一个；这样就完成了最大元素的位置确认。
 * --
 * 反思：
 * 即使进行了两种版本的优化，也不明显，最后的平均时间复杂度是 O(n^2)
 * --
 * 再次分析冒泡排序的性质：
 * 1.稳定的算法（无论多少次，相等的元素前后位置不变！）
 * 2.原地算法（空间复杂度 O(1)）
 */
public class BubbleSortV0 extends AbstractSort {


    @Override
    protected int[] sortArr(int[] arr) {
        int len=arr.length;
        for (int j = 0, end = arr.length-1; j < len; j++) {
            for (int i = 1; i <= end; i++) {
                if (arr[i - 1] > arr[i]) {
                    swap(arr, i - 1, i);
                }
            }
            //此时已经排序好一个
            end--;
        }
        return arr;
    }


}
